Граф
Граф:

• - мн-во вершин
• - мн-во рёбер
  Графы бывают:

Отображения, аналогичные тем, что даны для графов с кратными рёбрами, можно дать и для графов без кратных рёбер. В данном случае это будет означать, что отображение инъективно (каждой паре вершин соответствует ровно одно ребро, тогда как для графа с кратными рёбрами одной паре может соответствовать несколько рёбер)

Подграф
является подграфом графа , если:

3. и
   Или так, чтобы данная диаграмма была коммутативной:
   Аналогичным образом сохраняется отличие орграфа от неорграфа.

Примеры операций над графами, создающих подграфы:

• Исключение рёбер
• Исключение вершин (влечёт исключение рёбер с ней, иначе нарушается коммутативность диаграммы)
• Стягивания рёбер
  При такой операции ():

2. Удалённое ребро мы отображаем в вырожденное ребро (С,С).
   Потому и удобно считать, что вырожденные рёбра есть. Также можно задавать граф, используя множество обычных рёбер, дизъюнктно объединённое с множеством вырожденных рёбер, то есть рёбер вида . Или, что то же самое, дизъюнктно объединить с множеством вершин ().

Инцидентность
Пара вершина-ребро называется инцидентной, если вершина -- начало или конец ребра .

Степень вершины
Степенью (или порядком) вершины называется количество рёбер, инцидентных с вершиной.

• Минимальная степень вершины на графе:
• Максимальная степень вершины на графе:
  При подсчёте степени ребро-петля учитывается дважды.

Смежность

• Вершины называются смежными, если они соединены некоторым ребром
• Рёбра называются смежными, если они имеют общий конец
  Вершина и множество смежны, если и множество содержит вершину, смежную с . Два непересекающихся множества называются смежными, если существуют смежные вершины .

Окрестность

• -- окрестность вершины , то есть все вершины, смежные с ней.
• Для окрестностью называется множество всех вершин графа, смежных с . (Внутрь такой окрестности не входят вершины из самого !)

Подграф

• Остовный подграф G -- это такой подграф, в котором множество вершин совпадает с множеством вершин G
• Индуцированный подграф G -- это подграф, порождённый некоторым подмножеством , в котором остались рёбра, имеющие два конца на этом подмножестве

Висячая вершина
Это вершина со степенью 1

Дополнительный граф
Рассмотрим граф с тем же набором вершин, где все вершины соединены между собой (у каждой вершины степень ). Тогда дополнительным к графу на этих вершинах будет называться граф на тех же вершинах, рёбра которого есть в , но нет в .

Путь на графе
Пусть
Тогда путь на графе - это последовательность невырожденных рёбер , где:

2. Последовательность:

Путь длины ноль ведёт из вершины в неё саму
Цепь - путь, в котором рёбра не повторяются
Простая цепь, она же простой путь - путь, в котором не повторяются рёбра и вершины

"Определение"
Цикл - простая замкнутая цепь (то есть ). Разница в том, что в цепи есть выделенная вершина (цепь же идёт а -> b -> c -> a, выделенная вершина а как начало и конец цикла), а в цикле нет выделенных вершин, они там равноправны. Можно считать это отношением эквивалентности (цепь a -> b -> c -> a эквивалентна цепи b -> c -> a -> b и тд)

Теорема (без доква)
Если между вершинами есть путь, то они соединены простой цепью
Пояснение
На самом деле это достаточно простой факт. Он основан на том, что любой цикл можно просто удалить

Отношение достижимости
Путь на графе определяет отношение достижимости: это означает, что существует путь между двумя вершинами

• w достижима из v, если есть путь из v в w
  Это отношение рефлексивно и транзитивно, а если ещё и граф является неориентированным, то тогда это отношение эквивалентности (т.е. + симметричность). Классы эквивалентности в этом случае называются компонентами связности. При этом каждая компонента такого класса эквивалентности достижимых точек -- это подграф (порождённый вершинами из одного класса эквивалентности) исходного графа
• подграфконцы
  Важно, что элементами компоненты связности являются попарно связанные вершины. И если в неорграфе A -> B -> C -> D все четыре вершины являются отдельными компонентами связности, то в неорграфе А -- В -- С -- D это не так.

Отношение достижимости на орграфе является отношением предпорядка:
Отношение нестрогого порядка (): рефлексивное, антисимметричное, транзитивное
Отношение предпорядка: рефлексивное, транзитивное
Пусть отношение достижимости на орграфе. , если достижимо из . , если в обратную сторону тоже достижимо. Тогда -- рефлексивное, транзитивное, симметричное отношение
То есть -- отношение эквивалентности. Классы эквивалентности -- компоненты сильной связности. При этом пересечение таких компонент для неорграфа даст исходный граф, но вот для орграфа это не факт.

Матрица инцидентности для ографа
I(G), где G -- орграф. Матрица размера VxE (столбцы -- рёбра, строчки -- вершины) в которой (v,e) равна:

• 1, если t(e)=v (то есть ребро входит в вершину)
• -1, если s(e)=v (то есть ребро выходит из вершины)
• 0 иначе
  Для петли пишется 0. Петле таким образом отвечает нулевой столбец. Это не сильно удачно по причине того, что не указывается, в каком ребре есть петля.
  Это определение подходит и для графом с кратными рёбрами.

На неорграфе можно ввести ориентацию, потому что каждое ребро это технически два орребра
Для неорграфа часто считают, что компоненты берутся по модулю 2 (то есть -1 становится 1, то есть знак перестаёт влиять)

Матрица смежности
А(G) квадратная матрица VxV.

• Для неорграфа: (v,w) равна числу рёбер, ведущих из v -> w. По диагонали -- нули. Эта матрица симметрична
• Для орграфа: (v,w) разность между числом рёбер v -> w и числом рёбер в обратную сторону. Эта матрица кососимметрична. Обозначение []
  Ранее считали, что граф без петель. Однако если они есть, то тогда по диагонали тоже что-то пишется, причём считаем петлю дважды (для неорграфа, в орграфе по разности всё равно даст ноль). Важно, что матрица смежности для орграфа и для неорграфа разные и обозначаются по-разному.

Теорема
Для неорграфа без петель имеет следующий комбинаторный смысл:
Её компонента равна числу путей длины ведущих из
Также замечание: симметричная матрица, возведённая в степень, останется симметричной, поэтому является симметричной.
Доказательство
Индукция по q.

• q = 0. При возведении в нулевую степень даст единичную матрицу, что является количеством искомых путей
• q-1 -> q. Искомоечислопутей. Пример:
  \displaylines{ \begin{CD} \overset{A(G)^{q-1}} {\begin{bmatrix}
• & - & -\
• & - & -\
  X & X & X
  \end{bmatrix}} @.
  \overset{A(G)}
  {\begin{bmatrix}
• & X & -\
• & X & -\
• & X & -
  \end{bmatrix}}
  \end{CD}
  \\
  A(G)^q_{u_3,u_2} = [\text{Кол-во путей длины q-1 от u3 до u1}]\times[\text{Кол-по путей от u1 до u2}]\+[\text{Кол-во путей длины q-1 от u3 до u2}]\times[\text{Кол-по путей от u2 до u2}]\+[\text{Кол-во путей длины q-1 от u3 до u3}]\times[\text{Кол-по путей от u3 до u2}]}
  $$

Матрица Кирхгофа
Иное название - Лапласиан графа.
Рассмотрим теперь . Это матрица размером , причём симметричная, так как умножение любой матрицы на транспонированную даст симметричную матрицу. Результат произведения не будет зависеть от ориентации графа, поэтому можно взять в том числе любой неорграф и ввести на нём произвольную ориентацию. При выполнении произведения для мы фактически скалярно умножаем две строчки: u и w. Таким образом для каждого ребра мы смотрим, вышел ли путь из одной из этих точек и вошёл ли он во вторую. Если да, произведение будет равно -1, если путь вышел из одной вершины и ушёл в другую, или вышел из другой и пришёл в какую-то из них, или путь не начинался и не заканчивался на u или w, то тогда произведение равно нулю. Колворёберсоединяющихи. (то есть ведущих u->w или w->u). По диагонали у такой матрицы стоят степени вершин: этим она отличается от -A(G).

Лемма о рукопожатиях (для неорграфа)
Доказательство
Рассмотрим множество инцидентно. Посчитаем количество элементов в данном множестве:
Короче говоря, утверждение следует напрямую из того, что у каждого ребра ровно два конца.

Следствие
Количество вершин нечётной степени в любом графе чётно
Пояснения
Иначе бы получилось, что было бы нечётным, а оно всегда чётно по доказанной выше лемме

Рассмотрим неориентированный граф , а также: , , Количествокомпонентсвязности.

Определения дерева и леса

• Связный граф без циклов называется деревом.
• Граф без циклов (связный или несвязный) называется лесом. Лес может содержать множество несвязанных деревьев. Их количество равно данного леса.
• Мост в графе -- ребро, удаление которого увеличивает число компонент связности в графе.
• Остовный лес -- подграф с тем же множеством вершин, а отношение эквивалентности по достижимости даёт такие же компоненты связности (где множество рёбер -- подмножество исходного множества рёбер).
• Диаметр дерева -- максимальная длина кратчайшего пути между двумя вершинами в дереве

Ряд сведений о деревьях

• Любое ребро в лесу или в дереве является мостом (допустим, не так; тогда удалим ребро, которое не мост, а его концы будут находиться в одной компоненте связности; однако это означает наличие цикла, который замыкался удалённым ребром; аналогично доказательство с удалением вершин в циклах). Обратное утверждение также верно (Граф, в котором каждое ребро является мостом, является лесом)
• При стягивании вершин в лесу получается лес (допустим, не так; значит, у нас после стягивания появился цикл, но это значит, что цикл был изначально)
• Любой граф можно довести до остовного леса, выбросив все рёбра, которые не являются мостами

Предложение

2. равенствовыполненолес
   Доказательство
3. Индукция по числу рёбер. С 0 рёбрами всё работает. Теперь рассмотрим удаление ребра из случайного графа. В этом случае количество рёбер уменьшится на одно, а количество компонент связности или не увеличится, или увеличится на единицу (если удалён мост). То есть есть два варианта:
4. 1. Такая же индукция по числу рёбер. Для леса с нуля рёбрами равенство работает. Выбрасываем из дерева в лесу ребро. Получаем на одну компоненту связности больше и на одно ребро меньше. Получим . Здесь же мы доказали, что для любого леса выполняется именно равенство
   2. Допустим, равенство выполнено не для леса. Тогда начинаем выбрасывать не-мосты. Количество компонент связности не увеличится, а вот количество рёбер уменьшится. По итогу мы получим (по предположению, что любой граф приводится к остовному лесу) лес, в котором: . Однако мы уже доказали, что в любом дереве должно выполнятся равенство. Значит, изначально был не лес, то есть равенство выполнено тогда и только тогда, когда граф -- лес.

Теорема
В дереве с вершинами ровно ребро.
Доказательство

1. n=1. Работает
2. Добавляем вершину к дереву. По итогу увеличим и количество вершин, и количество рёбер на 1. То есть искомое соотношение сохранится

Ранг графа
Число называется рангом графа. Называется оно так по причине того, что это ранг матрицы инцидентности.
Пояснение
Матрица инцидентности строится относительно некоторой ориентации. В случае неографа ориентация может быть задана произвольно
Теорема
Доказательство

1. Заметим, что выкидывание не-моста не меняет ранг
   Рассмотрим такую картинку:
   Очевидно, что не является мостом. Помним, что каждое ребро -- это столбец в . Получим, что: , , . В линейной комбинации они как раз и дадут : . Этот случай уже записан в общем виде. Получается, что не-мост является линейно-зависимым от столбцов других участников цикла, а значит его исключение не уменьшит количество ЛНЗ столбцов и, следовательно, не изменит ранг. Важно помнить, что ориентация может быть любая. То есть, например, ребро может выглядеть и как , и как . Поэтому мы выбираем один из знаков: выбираем некоторое направление цикла и, если направление ориентации ребра совпадает с выбранным направлением берём с минусом, иначе -- с плюсом.
2. Благодаря пункту 1 достаточно рассмотреть данную теорему только для леса (потому что выкидывание не-мостов, то есть приведение к остовному лесу, не меняет обе части уравнения)
   Сгруппируем вершины и рёбра по их принадлежности к некоторой компоненте связности. Тогда матрица инцидентности будет иметь блочную структуру: те рёбра и вершины, что принадлежат одной компоненте, будут иметь на пересечении соответствующих строчек и столбцов значения , но те же строчки и столбцы в других местах будут иметь только значения ноль:
   перваякомпонентавтораякомпонентаперваякомпонентавтораякомпонента

При этом каждый блок является -- матрицей инцидентности компонент связности. Ранг общей матрицы становится равен сумме рангов таких вот матриц (потому что два столбца из разных блоков могут быть ЛЗ только если полностью нулевые, но они и так не посчитаются в ранг матрицы-блока, соответственно ранг общей матрицы равен количеству ЛНЗ столбцов матрицы, а значит равен количеству ЛНЗ столбцов к каждом блоке). Иным образом это можно сказать, продемонстрировав, что сумма пространства колонок каждого блока является прямой суммой.
3. [вариант док-ва от препода]. Докажем, что у любого дерева есть вершина степени 1, а если в нём есть рёбра, то их по крайней мере две. Для этого достаточно рассмотреть максимальный простой путь на данной графе. Если степень вершины не 1, то путь можно удлинить. Иначе степень равна 1. В итоге можно будет рассмотреть матрицы (при выкидывании висячей вершины связность не нарушается, используем ММИ):

\begin{CD}
x_0 @= x_1 @= x_2 @=x_3\
@| @| @| @| \
x_4 @= x_5 @= x_6 @= x_7\
@.@|@|@.\
@.x_8@=x_9
\end{CD}$$
Цикломатическое число равно трём, хотя количество циклов гораздо больше

Эйлеров путь -- это путь, проходящий по всем рёбрам графа ровно один раз

Эйлеров цикл -- это замкнутый путь, который проходит через каждое ребро графа по одному разу.
Граф, в котором существует Эйлеров цикл, называется Эйлеровым графом

Полуэйлеров граф -- граф, в котором существует эйлеров путь

Лемма
Если в графе степень каждой вершины чётна, то начиная с любого ребра можно начать цикл, который проходит через каждое ребро единожды (но может несколько раз пройти через вершину).
Доказательство

• Начнём обходить такой граф. Построим некоторый путь . Выбросим из изначального графа данный путь. Тогда степень вершины , если она не совпадает с , будет нечётной (в каждую вершину мы вошли столько же раз, сколько вышли, кроме ; даже если она совпадает с где-то в середине пути, в конце мы пришли в неё и не вышли). То, что в новом графе без данного пути степень нечётна означает, что она как минимум один, а значит у пути есть продолжение. Процесс, по условию , остановится тогда, когда .
  Пояснение

1. Это ещё не эйлеров цикл. Это цикл, в котором каждое ребро содержится единожды, но это совсем не означает, что содержатся все рёбра графа. Также мы можем считать, что этот цикл простой: ведь если есть не простой цикл, то можно убрать подцикл в нём и получить простой цикл, проходящий через данное ребро:
   Здесьмызафиксировалиребро

Теорема
ГрафЭйлеровГрафсвязанивсееговершиныимеютчётнуюстепеньДоказательство

1. => Эта часть аналогична лемме о рукопожатиях. Её результат: . (грубо говоря, мы в каждую вершину приходим столько же раз, сколько выходим из неё)
2. <=. Связность очевидна. Смотрим на чётность степеней вершин.
   • Рассмотрим замкнутый путь, проходящий через каждое ребро единожды, максимальной длины. Допустим, мы удалим этот путь из графа (точнее, удалим рёбра данного пути). Мы получим не обязательно связный граф, но граф с чётными степенями рёбер (потому что мы вычли чётное количество рёбер для каждой вершины).
   • Пусть мы выбросили не все рёбра. Тогда есть хотя бы одно ребро, смежное с вершиной, входившей в цикл (следует из связности, раз граф связный, а выброшены не все рёбра, то можно найти путь от случайного оставшегося ребра до цикла). При этом (по лемме) в оставшемся графе каждое ребро входит в простой цикл. Получается, что мы выбросили цикл не максимальной длины, ведь можно было не "пройти мимо" того смежного ребра, а пройти сначала весь замкнутый путь до вершины, в которую входит то смежное ребро, и пройти цикл, вернувшись в ту же вершину (как бы соединив эти циклы)
   • Получим противоречие. Получается, что все рёбра в этом максимальном цикле. А значит он эйлеров

Следствие (тривиальное)
Если граф несвязный, а все вершины имеют чётную степень, то это объединение непересекающихся эйлеровых циклов

Теорема
Рассматриваем связные графы
ГрафполуэйлеровГрафимеетиливершиныснечётнойстепеньюДоказательство

1. (=>) Если полуэйлеров путь замкнут, то этой эйлеров граф, нечётных вершин нет. Если незамкнут, то можно дополнить его одним ребром до замкнутости. Убирая обратно это ребро получим ровно две вершины с нечётной степенью
2. (<=) Если 0, то это эйлеров цикл, а значит граф эйлеров => полуэйлеров. Если две, то соединив эти вершины получим эйлеров цикл. Убирая добавленное ребро мы размыкаем эйлеров цикл, то есть получаем эйлеров путь

Произвольно вычерчиваемый граф
Эйлеров граф называется произвольно вычерчиваемым из вершины v, если любой путь с началом в этой вершине можно продолжить до эйлерового цикла.
Пример

Произвольно вычерчиваемый из :
Не произвольно вычерчиваемый из : нельзя продолжить до ЭЦ.

Предложение
произвольновычерчиваемизЛюбойпростойциклвпроходитчерезДоказательство

1. (=>). Допустим, не любой простой цикл проходит через . Значит, есть какой-то цикл, который не проходит через . Если выбросить этот цикл, то оставшийся граф будет эйлеровым (По лемме, так как каждая вершина четной степени). Обойдём его по этому эйлеровому циклу. Теперь вернём удалённый цикл, но обойти мы его уже никак не сможем. Значит, граф не вычерчиваемый (!!!)
2. (<=). Рассмотрим случайный путь . Вычеркнем его из графа. У нас может получится два случая:
   • . Тогда при вычёркивании данного пути-цикла мы получим эйлеров граф (все вершины останутся чётными).
   • . Так как изначальный граф эйлеров, то существует обратный эйлеров путь
     В изначальном графе существовала лишь одна компонента связности, а после вычёркивания данного пути их количество не увеличится (иначе был бы цикл, не проходящий через ). Значит компонента связности одна, причём граф или эйлеров, или полуэйлеров => есть обратный путь, который в объединение с изначальным даст эйлеров обход
     Пояснение
3. Граф - эйлеров
4. См. рисунок: “Pasted image 20240801151738.png” не может быть найдена.

Граф называется двудольным, если существует разбиение , а каждое ребро имеет вид (соединяет вершину из с вершиной из ).

Ещё один вариант определения: граф называется двудольным, если у него существует правильная раскраска в два цвета: вершины можно раскрасить в два цвета так, чтобы две вершины одного цвета не были смежными.

А если можно правильно раскрасить в k цветов, то есть покрасив в k цветов не получить рядом вершины одного цвета, то этот граф называется k-дольным

Критерий двудольности графа
ГрафдвудольныйвсециклывграфеимеютчётнуюдлинуДоказательство

1. (=>) Очевидно (потому что тогда рядом будут находиться вершины одного цвета, например, )
2. (<=) Выдумаем такую раскраску. Достаточно это сделать для одной КС, это легко распространяется на остальные. Оказывается, что любой пусть из в имеет одинаковую чётность длины (если это не так, то простой замкнутый путь [туда + обратно] имеет нечётную длину, то есть вершина окажется одновременно окрашенной в разные цвета, а не простой можно свести к рассмотрению повторяющейся вершины, у которой сумма двух путей нечётна, а значит один из путей [до той же вершины!] нечётен).

Два графа и называются изоморфными, если:Такие графы фактически являются разными способами задать один и тот же граф. Его комбинаторные свойства не меняются.

Важным признаком неизоморфности графов являются отличающиеся степени его вершин. Однако вполне могут существовать графы на вершинах с одинаковыми степенями, но не изоморфные друг другу

Ещё одним способом определять изоморфность графов: теорема Уитни

Точка сочленения
называется точкой сочленения в графе , если при её удалении увеличивается число компонент связности.
Пояснение
Вершина со степенью ноль не является ТС

Предложение
точкасочленениясуществуютизоднойКСнечтолюбойпутьпроходитчерезДоказательство
Тривиально. (=>) раз кол-во увеличилось, то есть такие точки, что связаны только через
(<=) Если это не ТС, то кол-во КС не должно увеличиться. Однако после удаления больше не будет путей. То есть увеличится

Замечание
В дереве любая не висячая вершина есть точка сочленения
Доказательство
Очевидно

Замечание
Любая точка цикла не является ТС
Доказательство
Очевидно

Блок
Блок -- максимальный по включению (по количеству точек, рёбра остаются теми же, что в изначальном графе) связный подграф без точек сочленения.
Пояснение

В этом графе ТС являются , а блоком может быть подграф

Замечание
В блоке с вершинами через любые две вершины проходит простой цикл
Доказательство (смотри пояснение)

• В данном блоке в принципе существует цикл[1]. Пусть он проходит через вершину . Докажем, что он тогда проходит и через любую другую вершину .
• Пусть имеется цикл , содержащий , а в него не входит. Раз имеется блок, то между и циклом есть путь. Рассмотрим точку внутри цикла, сопряжённую с этим путём, и точку из пути, сопряжённую с . Временно удалим точку . Она не являлась точкой сочленения, потому есть второй путь от до . "Перерисуем" цикл: теперь он будет идти от по новому пути до , из в , из в . “Pasted image 20240731004947.png” не может быть найдена.
• Точек, подобных , в указанном пути конечное число. Потому итеративно можно вычёркивать всё новые и новые точки до тех пор, пока не будет найден маршрут между и .
• Имеем: в блоке есть циклы. Есть циклы между конкретной и любой другой . Зафиксируем точку : тогда существует цикл между и любой точкой . Значит, через любые две вершины проходит простой цикл
  Пояснение

1. Иначе имеем дерево. В дереве на и более вершины есть как минимум одна не висячая. Пусть все висячие: тогда (по лемме о рукопожатиях)

Предложение
В блоке:

1. Через любые два ребра проходит цикл
2. Для любых двух данных вершин и одно данное ребро проходит простой путь
   Доказательство

• Условие (1) следует из (2). Возьмём одно ребро, а второе ребро рассмотрим как две его инцидентные вершины. По утверждению (2) они соединяются простым путём. Замыкая путь вторым ребром получим цикл. Значит и рёбра соединяются циклом
• Докажем второе утверждение. Зафиксируем ребро, проведём через него цикл[1]. Соединим вершины с этим циклом и найдём там простой путь “Pasted image 20240731005357.png” не может быть найдена.
  Следствие
• Для любых двух случайных вершин и третьей случайной вершины существует путь, проходящий из в через . [2]
• Для любых двух случайных вершин и третьей случайной вершины существует путь, проходящий из в , не проходящий через . [3]
  Пояснение

1. Это возможно, потому что через любые две вершины проходит цикл, в том числе и те, которые смежны. В итоге либо ребро лежит в цикле, либо цикл можно сократить, выбросив одну из частей и поставив вместо неё ребро (левая часть рисунка)
2. Рассмотрим вместо некоторое инцидентное с ним ребро. По условию есть путь из в через ребро, а значит и через саму .
3. Есть путь из в через . Просто отрезаем от него вторую часть пути

Теорема

1. Два блока имеют не более одной точки сочленения
2. Если при этом вершина принадлежит минимум двум блокам, то () она точка сочленения
   Доказательства

• Рассмотрим два блока с двумя общими вершинами. Объединим данные блоки. Получается, что удаление одной вершины не изменит связность графа[1]. Из этого следует, что два блока с двумя общими точками это на самом деле один и тот же блок (потому что блок - максимальный подграф).
• (Второе утверждение, =>) Раз так, то граф распался на несвязные. Потому что иначе у них было бы больше одной общей точки. А значит, она точка сочленения[2]
• (<=) Рассмотрим изначальную компоненту связности, содержавшую данную точку. Тогда после её удаления компонента распалась минимум на две. Рассмотрим теперь некогда существовавший путь A->Y->B. Где Y смежна с А и с В, при этом А в первой КС, а В во второй КС. Точки А и В находятся в разных блоках, потому что иначе бы имелся путь между ними, который не затрагивает Y, а тогда количество КС не увеличилось бы
  Пояснение

1. Вообще говоря, это очевидно. То, что было первым блоком, останется связным. И вторым тоже. А соединены они через вторую точку, которую мы не удаляли.
2. Ещё одна очевидная мысль. Рассмотрим "A->Y->B", где A лежит в первом блоке, B во втором, Y посередине и будет являться их общей точкой, причём смежной и с A, и с B. Если после удаления граф не потеряет связности, то есть ещё один путь между A->B. Тогда существует цикл, проходящий через A,Y,B и через другие точки обоих блоков. Тогда блок, состоящий их этого цикла, по наличию двух общих точек совпадает как с первым блоком, так и со вторым, что приравнивает все эти блоки друг с другом.

Дерево блоков и точек сочленения

Рассмотрим граф, в котором остаются лишь блоки, которые связаны со своими точками сочленения

Определение Пусть G связен. Обозначим  — блоки, а  — G. Построим двудольный граф TT, поместив  и  в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф T называют графом блоков-точек сочленения графа G.

Пояснение Почему дерево?

1. Существует последовательность точек сочленения и блоков, соединяющая  и  и не содержащая . По ней можно проложить путь в G (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине , получив цикл. Получается, что некоторые рёбра из  и  принадлежат одному и тому же циклу, что противоречит тому, что они находятся в разных блоках.